As described in U.S. patent application Ser. No. 10/839,995, which is incorporated by reference herein, a low-density parity-check (LDPC) code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over a Galois Field GF(q), q≧2. If q=2, the code is a binary code. As with all linear block codes, a k-bit information vector s1×k is generally encoded by the code generator matrix Gk×n to become an n-bit codeword x1×n, and the code rate is r=k/n. The codeword x is transmitted through a noisy channel, and the received signal vector y is passed to the decoder to estimate the information vector s1×k.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix Hm×n span the m-dimensional dual space C⊥, where m=n−k. Since x=sG and GHT=0, it follows that xHT=0 for all codewords in subspace C, where “T” denotes matrix transpose. In the discussion of LDPC codes, this is generally written asHxT=0T,  (1)where 0 is a row vector of all zeros, and the codeword x=[s p]=[s0, s1, . . . , sk−1, p0, p1, . . . , pm−1], where p0, . . . pm−1 are the parity-check bits; and s0, . . . sk−1 are the systematic bits, equal to the information bits within the information vector.
In a systematic code that maps k information bits to n coded bits, let the first k bits of the coded bits be the information bits. To make the code more flexible, shortening technique can be used to modify the code size. Shortening L bits modifies a (n, k) code to a lower rate (n−L, k−L) code utilizing part of the same H matrix. Without losing generality, in the following the shortened positions are assumed to be located in the first L information positions. When shortening L bits, the first L (0≦L<k) information bits are set to zero (logically or physically), and the corresponding zeros are removed from the coded bits after channel encoding. A code can be successively shortened to achieve a series of codes with descending code rates. In some encoders, leading zeros do not change the state of the encoder, so that the zeros do not have to be fed into the encoding circuit.
For an LDPC code, shortening by setting the first L information bits to zero can be accomplished in two equivalent ways. First, a k bit information vector (also known as systematic bits) can be set with the fist L bits being zero and the rest being the actual information bits to be encoded. The length k information vector can be fed into the encoder (which may be based on the unshortened (n−k)-by-n H matrix or the equivalent k-by-n generator matrix G), and the L zeros are subsequently stripped from the coded bits after encoding. Second, a shortened information vector may be passed to the encoder which encodes based on a shortened (n−k)-by-(n−L) H matrix with the first L columns removed, or the equivalent shortened (k−L)-by-(n−L) G matrix. In either case, the resulting shortened LDPC code(s) are likely to have poor performance because their weight distribution may be inferior to a code custom designed for that code rate and block size. It is not clear how to construct a shortened LDPC code that maintains good performance.
In order to use an LDPC code with good error-correcting performance, an appropriate low-density parity-check matrix H has to be defined. As is known in the art, better performance can be achieved by irregular rather than regular LDPC codes. It is found that irregular H matrices with good weight distribution have better performance than average, where the weight distribution specifies the fraction of columns with the given number of 1's, and the fraction of rows with the given number of 1's.
The term regular when used for an LDPC code means that all rows of H have a same number of 1's, and all the columns of H have a same number of 1's, where the number of 1's in a row or column is also called the weight of the row or column. Otherwise the LDPC code is considered irregular. In a narrower sense, the term regular can also be applied to either the rows or the columns (i.e., a matrix may have regular column weights, but irregular row weights), and can also be applied to a sub-matrix of a matrix (e.g., a submatrix of a matrix is regular when all the columns of the submatrix have the same column weight and all the rows of the submatrix have the same row weight). An example of applying irregular codes with good weight distribution for good performance is the digital video broadcasting satellite standard (DVB-S2) which defines multiple H matrices, each with the desired weight distribution for good performance at that code rate. The numbers of columns of each weight are shown in Table 1 for all the DVB-S2 code rates.
TABLE 1Number of Columns of Various Weights in DVB-S2.CodeRate13121184321¼540010800485991⅓720014400431991½1296019440323991⅗1296025920259191⅔432038880215991¾540043200161991⅘648045360129591⅚540048600107991 8/972005040071991 9/1064805184064791
In contrast to the DVB-S2 example, some code designs have only one H matrix and use shortening to achieve code rates, but the codes after shortening do not perform well. For instance, the portion of H corresponding to the information bits (denoted H1) is regular (and therefore the entire matrix is sometimes referred to as semi-regular), and after shortening the code weight distribution is poor compared to a good custom design. Therefore, a need exists for a method and apparatus for encoding and decoding data utilizing an H matrix that performs well with or without shortening.